package _20_十大排序算法;

import java.util.Arrays;

// 1 4 5 2
public class _03_插入排序 {

    public static void main(String[] args) {

        _03_插入排序 v = new _03_插入排序();
        int[] ins = new int[]{2, 3, 1, 5, 4, 2};

        v.insertSort2(ins);

        System.out.println(Arrays.toString(ins));
    }

    // 选择一个元素，插入另一部分的有序排序数组中
    public void insertSort(int[] nums) {
        // 假设第一个元素已经是排好序的
        for (int i = 1; i < nums.length; i++) {
            // 插入前面已经排好序的数组中
            int curIndex = i;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[curIndex] < nums[j]) {
                    swap(nums, curIndex, j);
                    curIndex = j;
                }
            }
        }
    }

    // 将交换元素，变成挪动元素
    public void insertSort1(int[] nums) {
        // 假设第一个元素已经是排好序的
        for (int i = 1; i < nums.length; i++) {
            // 插入前面已经排好序的数组中
            int curIndex = i;
            int value = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if (value < nums[j]) {
                    nums[curIndex] = nums[j];
                    curIndex = j;
                }
            }
            nums[curIndex] = value;
        }
    }

    // 使用二分搜索，搜索插入位置
    public void insertSort2(int[] nums) {
        // 假设第一个元素已经是排好序的
        for (int i = 1; i < nums.length; i++) {
            int insertEle = nums[i];
            // 插入前面已经排好序的数组中
            int insertIndex = searchIndex(nums, 0, i - 1, insertEle);
            // 移动元素
            if (i - insertIndex >= 0)
                System.arraycopy(nums, insertIndex, nums, insertIndex + 1, i - insertIndex);
            nums[insertIndex] = insertEle;
        }
    }

    public int searchIndex(int[] nums, int begin, int end, int target) {
        // 找到第一个大于等于目标值的数
        int result = end + 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) >> 1);
            if (nums[mid] >= target) {
                result = mid;
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }
        return result;
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
